package leetcode_401_500;

import com.sun.prism.ReadbackRenderTarget;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class LeeCode_494_better {
    public static void main(String[] args) {
//        System.out.println(findTargetSumWays(new int[]{1, 1, 1, 1, 1}, 3));
//        System.out.println(findTargetSumWays(new int[]{1}, 1));
//        System.out.println(findTargetSumWays(new int[]{1, 0}, 1));
//        System.out.println(findTargetSumWays(new int[]{0,0,0,0,0,0,0,0,1}, 1));
//        System.out.println(findTargetSumWays(new int[]{0,0,0,0,0,0,0,0,1}, 1));
//        System.out.println(findTargetSumWays(new int[]{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, 1));
        System.out.println(findTargetSumWays(new int[]{0,0,0,0,0,0,0,1000}, 1000));
    }
    private static int findTargetSumWays(int[] nums, int target) {
        for (int num : nums) {
            target += num;
        }
        if(target < 0 || target % 2 == 1)
            return 0;
        target /= 2;

        int n = nums.length;
        int[][] cache = new int[n][target + 1];
        for (int i = 0; i < n; i++) {
            Arrays.fill(cache[i], -1);
        }
        return dfs(nums, cache, n - 1, target);
    }
    private static int dfs(int[] nums, int[][] cache, int i, int c){
        if (i < 0)
            return c == 0 ? 1 : 0;
        if (cache[i][c] != -1)
            return cache[i][c];
        if (c < nums[i])
            return cache[i][c] = dfs(nums, cache, i - 1, c);
        return cache[i][c] = dfs(nums, cache, i - 1, c) + dfs(nums, cache, i - 1, c - nums[i]);
    }
}
